'''
素数筛
复杂度nloglog
'''
MAX = 1000000
# 不是质数
isnp = [0] * MAX

'''
初始化素数范围不超过n
'''


def init(n):
    for i in range(2, n + 1):
        if not isnp[i]:
            j = i * i
            while j <= n:
                isnp[j] = 1
                j += i


'''
欧式筛,mp[i] 为i的最小质因子
注意此处是list记录代码，不能用set
'''


def getPrimes():
    N = 100000
    sub = [0] * (N + 1)
    primes = list()
    for i in range(2, N + 1):
        if not sub[i]:
            primes.append(i)
            sub[i] = i
        for p in primes:
            if p * i > N: break
            sub[p * i] = p
            if i % p == 0: break
    return primes


'''
判断是否为质数
'''

def isPrime(a):
    if a <= 1: return False
    i = 2
    while i * i <= a and a % i != 0:
        i += 1
    return i * i > a


'''
所有因数

'''
def getDivisors(n):
    ans = []
    i = 1
    while i * i <= n:
        if n % i == 0:
            ans.append(i)
            if i * i < n:
                ans.append(n // i)
        i += 1
    return ans


'''
质因式分解
'''


def factorization(n):
    ans = []
    i = 2
    while i * i <= n:
        if n % i == 0:
            while n % i == 0:
                n //= i
                ans.append(i)
        i += 1
    if n > 1:
        ans.append(n)
    return ans


'''
最小质因数,n是奇数,偶数的话就是2
'''


def minPrime(n):
    i = 2
    ans = -1
    while i <= n // i:
        if n % i == 0:
            return i
        i += 1
    if n & 1:
        ans = n
    return ans


'''
判断[a,b] 之间是否有数字可以被k整除
'''


def containK(k, a, b):
    # x 向上取整,y 向下取整
    x = (a + k - 1) // k
    y = b // k
    return x <= y

'''
-------------------------------------------------

'''
def prime_range(n):
    sieve = [True] * n
    p = []
    for i in range(2, n):
        if sieve[i]:
            p.append(i)
            for j in range(i * i, n, i):
                sieve[j] = False
    return p

p = prime_range(int((10 ** 9) ** 0.5) + 1)


def num_prime_factors(a):
    f = 0
    for x in p:
        if x * x > a:
            break
        while a % x == 0:
            a //= x
            f += 1
    if a > 1:
        f += 1
    return f
'''
----------------------------------------------------
'''



